package bintree.heap.leetcode;

/**
 * @Author: yuisama
 * @Date: 2021/9/13 15:08
 * @Description:经典的TopK问题
 * 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
 * 示例：
 * 输入： arr = [1,3,5,7,2,4,6,8], k = 4
 * 输出： [1,2,3,4]
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/smallest-k-lcci
 */
public class TopK {
    /**
     * 找最小的建大堆，找最大的建小堆
     * @param arr
     * @param k
     * @return
     */
//    public int[] smallestK(int[] arr, int k) {
//        if (arr.length <= 0 || arr.length < k) {
//            return arr;
//        }
//        if (k <= 0) {
//            return new int[0];
//        }
//        int[] ret = new int[k];
//        // 建立k个数据大小的大堆，开始从k+1个位置遍历集合，遍历结束后，堆中存储的是最小的k个元素
//        PriorityQueue<Integer> queue = new PriorityQueue<>((t1,t2) -> t2 - t1);
//        for (int i = 0; i < k; i++) {
//            queue.offer(arr[i]);
//        }
//        // 从第k + 1个元素开始遍历，比堆顶元素小的入队列
//        for (int i = k; i < arr.length; i++) {
//            if (arr[i] < queue.peek()) {
//                // 堆顶元素出队
//                queue.poll();
//                // 将当前元素入队
//                queue.offer(arr[i]);
//            }
//        }
//        // 遍历结束，此时堆中存储的是集合中最小的k个元素
//        for (int i = 0; i < k; i++) {
//            ret[i] = queue.poll();
//        }
//        return ret;
//    }

    /**
     * 快排分区思想解决最小k个数
     * 随机选取的分区点若恰好是第k + 1大的元素，则分区点左侧就是前k个最小的数
     * @param arr
     * @param k
     * @return
     */
    int k;
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        this.k = k;
        if (arr.length == 0) {
            return ret;
        }
        quickSort(arr,0,arr.length - 1);
        for (int i = 0; i < k; i++) {
            ret[i] = arr[i];
        }
        return ret;
    }

    private void quickSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int pivot = arr[l];
        int i = l;
        int j = r;
        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j --;
            }
            arr[i] = arr[j];
            while (i < j && arr[i] <= pivot) {
                i ++;
            }
            arr[j] = arr[i];
        }
        arr[i] = pivot;
        if (i == k) {
            return;
        }
        if (i > k) {
            quickSort(arr,l,i - 1);
        }
        if (i < k) {
            quickSort(arr,i + 1,r);
        }
    }

//    private void quickSort(int[] arr, int l, int r) {
//        int randomIndex = new Random().nextInt(r - l + 1) + l;
//        swap(arr,l,randomIndex);
//        int v = arr[l];
//        int j = l;
//        for (int i = l + 1; i <= r; i++) {
//            if (arr[i] < v) {
//                swap(arr,i,j + 1);
//                j ++;
//            }
//        }
//        swap(arr,l,j);
//        // 注意，这里j是索引，因此若j左侧恰好有k个元素 < j，则j就是排序后数组第k + 1大的元素
//        // 因此当j恰好==k时，索引j的左侧恰好有k个元素
//        if (j > this.k) {
//            // 分区点左侧元素 > k个,继续缩小分区点在左侧重新分区
//            quickSort(arr,l,j - 1);
//        }
//        if (j < this.k) {
//            // 分区点左侧元素 < k个，继续在右侧分区
//            quickSort(arr,j + 1,r);
//        }
//    }

    public void swap(int[] arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
